package 力扣.树.后序遍历;

public class 二叉搜索树的后序遍历序列Offer33 {
    public boolean verifyPostorder(int[] postorder) {
        if (postorder == null){
            return false;
        }
        if (postorder.length == 0){
            return true;
        }
        return recur2(postorder,0,postorder.length -1);

    }
    //如何寻找根节点并划分左右子树？
    // 寻找第一个大于根节点的数，记录下标为m,则划分左右子树分别为[i,m)、[m,根节点)
    // 接着递归判断左右子树
    private boolean recur2(int[] postorder,int i,int j){
        if (i >= j){//只剩下一个节点，‘i  >= j -1’也可以，任意两个数其实都可以构成后序遍历
            return true;
        }
        int p = i;
        while (postorder[p] < postorder[j]){//寻找第一个大于post[j]的元素，作为左右子树的分界线
            p++;
        }
        int m = p;//左子树[i,m-1] 右子树[m,j -1]
        //判断左右子树是否满足二叉树的后序遍历：左子树都小于根节点，右子树都大于根节点
        //左子树：在寻找m时已经满足条件了
        while (postorder[p] > postorder[j]){//右子树：判断右子树所有节点是否都大于根节点
            p++;
        }
        //判断p是否是根节点（证明右子树都大于根节点） && 递归判断左子树 && 递归判断右子树
        return p == j && recur2(postorder, i, m - 1) && recur2(postorder, m, j - 1);
    }

}
